package backTrack;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.LinkedList;

//leetcode submit region begin(Prohibit modification and deletion)
class Class39 {
    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<Integer>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        backTracking(candidates, target, 0, 0);
        return result;
    }

    public void backTracking(int[] candidates, int target, int start, int sum) {
        if (sum > target) {
            return;
        }
        if (sum == target) {
            result.add(new ArrayList<>(path));
            return;
        }
        int length = candidates.length;
        //  CKG TODO 2023/4/22: for循环控制宽度 里面的backtracking 控制深度
        for (int i = start; i < length; i++) {
            path.add(candidates[i]);
            sum += candidates[i];
//            if (sum>target){
//                break;
//            }
            //  CKG TODO 2023/4/22:   这个地方的确 从i开始    要是从start开始每轮都是把数组里的元素都来一遍有重复
            backTracking(candidates, target, i, sum);
            sum -= candidates[i];
            path.removeLast();
        }
    }


    public static void main(String[] args) {
        Class39 class39 = new Class39();
        int[] arr={2,3,6,7};
        List<List<Integer>> lists = class39.combinationSum(arr, 7);
        System.out.println(lists.toString());
    }



}
